02. Solving a Sudoku

What is a Sudoku?

Sudoku is one of the world's most popular puzzles. It consists of a 9x9 grid, and the objective is to fill the grid with digits in such a way that each row, each column, and each of the 9 principal 3x3 subsquares contains all of the digits from 1 to 9. The detailed rules can be found, for example, here.

The puzzle is given as a partially completed grid, and the goal is to fill in the missing numbers. Below is an example of such a grid.

Goals of this project

The main goal of this project is to build an intelligent agent that will solve every sudoku while introducing you to two powerful techniques that are used throughout the field of AI:

• Constraint Propagation
  
  When trying to solve a problem, you'll find that there are some local constraints to each square. These constraints help you narrow the possibilities for the answer, which can be very helpful. We will learn to extract the maximum information out of these constraints in order to get closer to our solution. Additionally, you'll see how we can repeatedly apply simple constraints to iteratively narrow the search space of possible solutions. Constraint propagation can be used to solve a variety of problems such as calendar scheduling, and cryptographic puzzles.
• Search
  
  In the process of problem solving, we may get to the point where two or more possibilities are available. What do we do? What if we branch out and consider both of them? Maybe one of them will lead us to a position in which three or more possibilities are available. Then, we can branch out again. At the end, we can create a whole tree of possibilities and find ways to traverse the tree until we find our solution. This is an example of how search can be used.

These ideas may seem simple and they're actually intended to be! Through this lesson you'll see how AI is really composed of very simple ideas that can be put together to solve complex problems. Throughout this lesson, we challenge you to think of how you can apply these ideas to build AI agents to solve other puzzles and problems in your world!

Udacity Project Reviews

Another goal of this project is to get you familiarized with the submission process at Udacity. The AI Nanodegree program includes some self-graded exercises, some autograded exercises, and projects that are reviewed by one of our talented reviewers. The sudoku project is primarily autograded, although we have human reviewers available as backup. Most importantly, you'll be able to have fun as you use the power of AI to solve familiar problems and, in the process, compare how an AI agent thinks like a human!

Hands on!

Let's get started by trying to solve a sudoku puzzle ourselves. Doing so will allow us to discover and become comfortable with the techniques that our agent may end up using.

Copy down the Sudoku puzzle below and try to solve it. If you don't finish, it's ok. The solution is on the next page. But as you attempt to solve it, try to pick apart the techniques you use, as they may form part of your intelligent agent.

Ready? Pen? Paper? Let's go!